#include <iostream>
#include <cstdio>
using namespace std;
typedef __int128_t LLL;
LLL dp[2007];
LLL MOD = 2000000000000000003;
int main(int argc, char** argv) {
    int t;
    cin>>t;
    while (t--) {
        int ask;
        cin>>ask;
        dp[0] = 1;
        for (int i=1; i<=ask; ++i) {
            dp[i] = i;
            dp[i] = max(dp[i], dp[i/2]*dp[i-i/2]);
            dp[i] = max(dp[i], dp[i/2+1]*dp[i-i/2-1]);
            dp[i] = max(dp[i], dp[i/2-1]*dp[i-i/2+1]);
            dp[i] = dp[i] % MOD;
        }
        cout<<(long long)dp[ask]<<endl;
    }
    return 0;
}
